#ifndef P2_H
#define P2_H
#include <iostream>
#include <vector>
#include <list>
#include <fstream>
#include <stdlib.h>
#include <sstream>
#include <iterator>
#include <algorithm>


#define ITER 100000

#ifdef __amd64
inline uint64_t rdtsc(){
	uint32_t lo, hi;
	__asm__ __volatile__ (
	"xorl %%eax, %%eax\n"
	"cpuid\n"
	"rdtsc\n"
	: "=a" (lo), "=d" (hi)
	:
	: "%ebx", "%ecx" );
	return (uint64_t)hi << 32 | lo;
}
#endif


using namespace std;

struct camino{
	int c1;
	int c2;
	int costo;
	camino(){}
	camino(int i, int j, int k):c1(i),c2(j),costo(k){}

	bool operator<(const camino& c) const{
		return costo < c.costo;	
	}
};

struct nodo{
	nodo* padre;
	int altura;
};

class bosque{
	

	vector<nodo*> arboles;
	
	public:	
		bosque(){}
		bosque(int c);
		~bosque();
		
	//Devuelve false si las 2 ciudades pertenecen al mismo arbol
	// y devuelve True si pertenecen a distintos y entonces los combina en un solo arbol
	// poniendo al arbol mas chico como hijo de la raiz del arbol mas grande (en cantidad de nodos)
		bool combinar(int c1,int c2);
};

list<camino> cargar(istringstream& is, int n);
int resolver(const int n, const list<camino> &caminos,list<camino> &solucion);
void salida(ostream& out, int sol,list<camino> &solCaminos);

#endif // P2_H
